package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

import java.util.Arrays;

/**
 * @author tzp
 * @since 2020/9/22
 */
public class LC416 implements DynamicProblem {
    public boolean canPartition(int[] nums) {
        Arrays.sort(nums);
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false;
        int half = sum / 2;
        int[][] dp = new int[nums.length][half + 1];
        return re(nums, dp, 0, half) == 1;
    }

    public int re(int[] nums, int[][] dp, int start, int target) {
        if (start >= nums.length) return 2;
        if (target < 0) return 2;
        if (dp[start][target] != 0) return dp[start][target];

        if (nums[start] == target) {
            dp[start][target] = 1;
            return 1;
        }

        if (re(nums, dp, start + 1, target) == 1) {
            dp[start][target] = 1;
            return 1;
        }

        if (re(nums, dp, start + 1, target - nums[start]) == 1) {
            dp[start][target] = 1;
            return 1;
        }
        dp[start][target] = 2;
        return 2;
    }

    public static void main(String[] args) {
//        System.out.println(new LC416().canPartition(new int[]{1, 5, 11, 5}));
//        System.out.println(new LC416().canPartition(new int[]{1, 2, 5}));
//        System.out.println(new LC416().canPartition(new int[]{2, 2, 3, 5}));
        System.out.println(new LC416().canPartition(new int[]{100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}));
    }
}
